package lc.链表;

import utils.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @description:
 * @author: qian
 * @createDate: 2021/10/23
 */
public class 剑指Offer52_两个链表的第一个公共节点 {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

        Set<ListNode> set = new HashSet<>();
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }
        while (headB != null && !set.contains(headB)) {
            headB = headB.next;
        }
        return headB;
    }


    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        // 两个结点不断的去对方的轨迹中寻找对方的身影，只要二人有交集，就终会相遇
        ListNode n1 = headA;
        ListNode n2 = headB;
        while (n1 != n2) {
            n1 = n1 == null ? headB : n1.next;
            n2 = n2 == null ? headA : n2.next;
        }
        return n2;
    }
}
